1286A - Garland - CodeForces Solution

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
  int n;
  scanf("%d",&n);
  int ganjil=(n+1)/2;
  int genap=(n/2);
  int arr[n+5];
  for(int a=1;a<=n;a++)
  {
    scanf("%d",&arr[a]);

  }
  int dp[n+4][ganjil+5][genap+5][2];
  for(int a=0;a<=n;a++)
    for(int b=0;b<=ganjil;b++)
      for(int c=0;c<=genap;c++)
        for(int d=0;d<=1;d++)
          dp[a][b][c][d]=1e9;
  dp[0][0][0][0]=0;
  dp[0][0][0][1]=0;

  // panjang , sisa ganjil, sisa genap,sebelumnya, sekarang;
  for(int a=1;a<=n;a++)
  {
    for(int b=0;b<=ganjil;b++)
    {
      for(int c=0;c<=genap;c++)
      {
        for(int e=0;e<=1;e++)
        {
            if(b==0 && c==0)
            continue;
            if(b==0 && e==1)
            continue;
            if(c==0 && e==0)
            continue;
            if(arr[a])
            {
              if(arr[a]%2==1 && e==0)
              continue;
              if(arr[a]%2==0 && e==1)
              continue;
            }
            if(e==0)// kalau enya genap
            {

              dp[a][b][c][e]=min(dp[a-1][b][c-1][e],dp[a][b][c][e]);
              dp[a][b][c][e]=min(1+dp[a-1][b][c-1][1],dp[a][b][c][e]);
            }
            if(e==1)// kalau enya ganjil
            {

              dp[a][b][c][e]=min(dp[a-1][b-1][c][e],dp[a][b][c][e]);
              dp[a][b][c][e]=min(1+dp[a-1][b-1][c][0],dp[a][b][c][e]);
            }
            if(a==1 && dp[a][b][c][e]>=0)
            dp[a][b][c][e]=0;
          
        }
        
      }
    }
  }
//  for(int a=0;a<=n;a++)
//    for(int b=0;b<=ganjil;b++)
//      for(int c=0;c<=genap;c++)
//        for(int d=0;d<=1;d++)
//          printf("dp[%d][%d][%d][%d]=%d\n",a,b,c,d,dp[a][b][c][d]);
//  int maks=-1e9;
  if(arr[n])
  {
    if(arr[n]&1)
    printf("%d\n",dp[n][ganjil][genap][1]);
    else
    printf("%d\n",dp[n][ganjil][genap][0]);  
  }
  else
  printf("%d\n",min(dp[n][ganjil][genap][1],dp[n][ganjil][genap][0]));
  
//  printf("%d\n",maks);
}